package com.hjx.other;

/**
 *
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memoization/1214/
 * @author houjinxin
 * @version 创建时间：2019/11/5.
 */
public class PaLouTi {

    /**
     * 方法一：暴力法
     * 算法
     *
     * 在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。
     * 而在每一步中我们都会继续调用 climbStairs 这个函数模拟爬 1 阶和 2 阶的情形，并返回两个函数的返回值之和。
     *
     * climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)
     *
     * 其中 i 定义了当前阶数，而 n 定义了目标阶数。
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }

    public int climb_Stairs(int i, int n, int[] memo) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }


    /**
     * 到第i阶可以由以下两种方法
     * 1、第i-1阶向上爬一阶
     * 2、第i-2阶向上爬二阶
     * 即到第i阶的方法总数 等于 到i-1 和 i-2 阶的方法总数的和
     * dp[i] = dp[i-1] +  dp[i-2]
     *
     * @param n
     * @return
     */
    public int climbStairs1(int n){
        //一阶只有一种方法
        if (n == 1){
            return 1;
        }

        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    public int climbStairs2(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }

    public static void main(String[] args) {
        System.out.println(new PaLouTi().climbStairs1(5));
    }
}
